/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

// 2020.8.11 town 

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (k == 1){
            return head;
        }
        int len = 0;
        ListNode* begin = head;
        ListNode* end = head;
        ListNode* last = NULL;
        ListNode* tmp = NULL;
        ListNode* res = NULL;
        while(end != NULL){
            len++;
            if (len == k){
                if(res == NULL){
                    res = end;
                }
                tmp = end -> next;
                reverse(begin, end);
                //cout<<"begin:"<<begin->val<<" ";
                //cout<<"end:"<<end->val<<endl;
                if(last != NULL){
                    last -> next = end;
                }
                last = begin;
                len = 0;
                //cout<<"new begin/end:"<<tmp->val<<endl;
                begin = tmp;
                end = tmp;
                last -> next = tmp;
            } else{
                end = end -> next;
            }
        }
        return res;
        

    }

private:
    void reverse(ListNode* b, ListNode* e) {
        ListNode* cur = b->next;
        ListNode* tmp = NULL;
        ListNode* last = b;
        //b->next = e->next;
        while(cur != e){
            tmp = cur->next;
            cur->next = last;
            last = cur;
            cur = tmp;
        }
        e -> next = last;
        /*
        ListNode* test = e;
        while(test != b){
            cout<<test->val<<" ";
            test = test->next;
        }
        cout<<b->val<<" ";
        cout<<endl;
        */
    }
};

/*
stack 栈
*/
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        stack<ListNode*> mystack;
        ListNode* newhead = new ListNode(0);
        ListNode* last = newhead;
        ListNode* cur = head;
        int len = 0;
        while (true){
            while(cur != NULL && len < k){
                mystack.push(cur);
                len++;
                cur = cur -> next;
            }
            
            if (len != k){
                break;
            }
            len = 0;
            
            while(!mystack.empty()){
                last -> next = mystack.top();
                last = mystack.top();
                mystack.pop();
            }
            last -> next = cur;
        }
        return newhead->next;
    }
};